package cn.micai.base.math;

/**
 * @author zhaoxinguo on 2018/4/9.
 * @email sxdtzhaoxinguo@163.com
 * @qq 827358369
 * @phone 18611966723
 * @description
 */
public class MyOrderArray {

    private long [] arr;

    // 表示有效数据的长度
    private int elements;

    public MyOrderArray() {
        arr = new long[50];
    }

    public MyOrderArray(int maxSize) {
        arr = new long[maxSize];
    }

    /**
     * 添加数据 构建有序数组，按从小到大排序
     * @param value
     */
    public void insert(long value) {
        int i;
        for (i = 0; i < elements; i++) {
            if (arr[i] > value) {
                break;
            }
        }

        for (int j = elements; j > i; j--) {
            arr[j] = arr[j -1];
        }

        arr[i] = value;
        elements++;

    }

    /**
     * 二分法查找，前提是必须是有序数组
     * @param value
     */
    public int binarySearch(long value) {
        int middle = 0; // 中间值
        int low = 0; // 最左边值
        int pow = elements; // 最大值

        while (true) {
            middle = (pow + low) / 2;
            if (arr[middle] == value) {
                return middle;
            } else if (low > pow) {
                return -1;
            } else {
                if (arr[middle] > value) {
                    // 往左边走
                    pow = middle - 1;
                } else {
                    // 往右边走
                    low = middle + 1;
                }
            }
        }
    }

    /**
     * 显示数据
     */
    public void display() {
        System.out.print("{");
        for (int i=0; i< elements; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println("}");
    }

    /**
     * 查找数据，根据值查找
     */
    public int search(long value) {
        int i;
        for (i = 0; i< elements; i++) {
            if (value == arr[i]) {
                break;
            }
        }
        if (i == elements) {
            return -1;
        } else {
            return i;
        }
    }

    /**
     * 查找数据，根据索引查找
     * @param index
     * @return
     */
    public long get(int index) {
        if (index >= elements || index < 0) {
            throw new ArrayIndexOutOfBoundsException();
        } else {
            return arr[index];
        }
    }

    /**
     * 删除数据，根据索引删除
     * @param index
     */
    public void delete(int index) {
        if (index >= elements || index < 0) {
            throw new ArrayIndexOutOfBoundsException();
        } else {
            for (int i= index; i < elements; i++) {
                arr[index] = arr[index + 1];
            }
            elements--;
        }
    }

    /**
     * 更新数据
     * @param index
     * @param newvalue
     */
    public void change(int index, int newvalue) {
        if (index >= elements || index < 0) {
            throw new ArrayIndexOutOfBoundsException();
        } else {
            arr[index] = newvalue;
        }
    }

}
